The present invention relates to medium access control sublayer protocols for a shared medium, and more particularly to carrier sense multiple access with collision detection (CSMA/CD) protocols.
In any network in which multiple hosts are connected to a single shared communications channel (a multiaccess system), there must be a method to resolve which host gets to use the channel when there is contention. In a multiaccess system, data sent by one host will be received by all other hosts. However, if two different hosts attempt to transmit data simultaneously, there is a collision, and the data is lost. The various methods to resolve contests between the hosts and recover from collisions are called Medium Access Control (MAC) sublayer protocols.
Protocols in which multiple hosts listen for a carrier (i.e. a transmission) to determine whether the channel is currently busy are called carrier sense multiple access (CSMA) protocols. By waiting until the channel is free to begin transmitting, some collisions are avoided.
One type of CSMA protocol is the 1-persistent CSMA. In this protocol, when a host has data to transmit, it listens to the channel. If the channel is busy, then the host continuously monitors the channel until it becomes idle. Once the channel is idle, the host begins to transmit its data. If there is a collision, each host waits a random amount of time after a collision before trying again. One host will win the contest by picking the shorter internal of time. A collision occurs only if the two hosts pick identical numbers, or if a new host joins. In another variation called a P-persistent CSMA, the host has a certain probability p of transmitting data, and a probability of 1-p of waiting for a set period.
An improvement over standard CSMA protocol is for the host to cease transmitting immediately if it detects a collision. By ending transmissions after a collision is detected, time and bandwidth is conserved. These protocols are called CSMA/CD protocols. A host may detect a collision by comparing the data that it transmits to the signal it measures on the channel.
Collisions do occur in the 1-persistent CSMA/CD. First, the propagation delay on the channel may create collisions. If a second host becomes ready to transmit after a first host begins sending, but before the first host's signal reaches the second host then the second host will detect the channel as idle, begin transmitting and cause a collision. Second, even if the propagation delay is small, two or more that are ready to transmit data at then end of another transmission will do so simultaneously, resulting in a collision. Although a P-persistent CSMA/CD protocol reduces the chance of simultaneous transmissions by new hosts, there is still a probability of P.sub.2 (for two active hosts) of collision.
The Institute of Electrical and Electronics Engineers (IEEE) has produced several standards for MAC protocols. IEEE Standard 802.3 has been universally adopted for the 1-persistent CSMA/CD protocol. In the 802.3 Standard, each host that has data to transmit waits until it detects an idle channel, and then begins transmitting.
The 802.3 Standard uses the binary exponential backoff (BEB) method to dynamically adapt to the number of hosts trying to send to reduce collisions. If a host detects a collision, it waits a random integer number of "slot times" before repeating the cycle. The slot time is defined as the time required to transmit 512 bits over the network. This value was determined by the worst case round trip propagation delay between hosts allowed by Standard 802.3 for 10 Mbps networks, and has been preserved in the new Standard 802.3u for 100 Mbps networks.
If two different hosts pick the same random number of slot times, a second collision will occur. The maximum random number increases as the number of collisions increases. In the BEB method, the random number is between zero and 2.sup.min(n.10) -1, where the counter n is the number of collisions experienced by this packet. Therefore, after the first collision, the host waits zero or one slot time. After the second collision, the host waits zero, one, two, or three slot times. However, after 10 collisions, the maximum random number is frozen at 1023. In addition, after 16 collisions, the controller reports a failure back to the host. Following a successful transmission, the counter n in the successful host is reset to zero.
The MAC sublayer protocol currently used with Ethernet can cause significant performance problems. Since collisions waste channel bandwidth, it is vital that the number of collisions be minimized to decrease the load on the channel. In addition, collisions can generate more collisions through positive feedback when the retransmitted packets compete with later arrivals. A protocol may be described as stable if it avoids the positive feedback effect. Unfortunately, it is not clear whether Ethernet's BEB method is stable.
Even if Ethernet's BEB method is stable, the dynamics represent a poor scheduling discipline. The BEB method results in a reverse lottery in which certain packets are selected for exceptionally long delays, while most other packets are transmitted as soon as they reach the head of the transmit queue.
It is important to distinguish the perceptions of the service provider from the user. The primary concern of the service provider is throughput; whenever there is data in the system in need of transmission, the network should be engaged in delivering it. The users, on the other hand, are primarily concerned with delay. Delay consists both of waiting time, the time that elapses from the generation of a data packet to its arrival at the head of the transmit queue, and access time, the time that data packet spends at the head of the transmit queue. Human users have a strong dislike for unpredictability. In many applications, such as voice or video, delay variance is as important as the average delay.
Under BEB, the collision counter (equal to number n above) of a given host is updated only in response to actual transmission attempts by that host. Consider several active hosts each with several data packets in its queue. Once there is a successful packet transmission, only the "winner" will reset its collision counter to zero. First, the winning host is free to transmit its next packet immediately, while other hosts may have a retry time that is longer than the transmission packet time. Second, at the next collision, the winner randomly selects its retry time from the smallest possible interval, whereas the other hosts randomize their retry times over a much larger interval. Therefore, the first winning host is likely to capture the network repeatedly until its transmit queue is empty. Those host which have transmitted recently are about one-hundred times more likely to acquire the channel than others. This "last-in, first-out" system results in unacceptable variations in the delay time. Modifications to BEB have been proposed in order to eliminate the unfairness of the capture effect in the standard protocol, but their effectiveness is limited to networks with two nodes. In addition, BEB could be avoided by using published methods to stabilize CSMA protocols using a conflict resolution algorithm. However, these alternatives are not interoperable with the Standard 802.3 protocol. Furthermore, they require the hosts to monitor the channel continuously for a very long time, and/or suffer from the same "last-in, first-out" unfairness as BEB.
On the other hand, a capture effect may help system performance in certain circumstances. Under reasonably heavy load conditions, allowing a single host to capture the channel reduces the relative amount of time spent resolving contests. This increases the percentage time that the channel is engaged in delivering data and improves throughput.
However, the current MAC protocol for Ethernet is not a work conserving scheduler. In a work conserving system the shared resource is always engaged in useful activity, if there is at any host waiting to use the channel. However, the BEB method does not conserve work during periods of congestion. Some unlucky hosts will suffer multiple collisions, take a large backoff delay time, and "sleep" through the end of a congested period. Consequently, the resource will be sitting idle even though there is data waiting to be transmitted.
Also, the BEB method is slow in adapting to transient overload conditions. On occasion, a large number of hosts may start transmitting simultaneously. In the BEB method the average time to the first successful transmission after such an overload is linearly proportional to the number of active hosts.
Furthermore, the BEB method is not capable of handling the Ethernet standard maximum of hosts. In fact, the BEB method is bistable with more than 225 hosts, and is unstable with more than several hundred hosts. In a situation where a large number of hosts attempt to transmit packets at the same time, the system may enter a degraded operating mode in which almost every attempt to send data results in a collision, delaying a successful transmission indefinitely. The degenerated operating mode is particularly likely if the number of hosts is much larger than 225. This is because in the degenerated operating mode, the probability that a given host transmits in each slot is approximately 1/225. One may compute this figure by summing the average number of slots it takes for a single host to "wrap around" on the sixteenth collision.
An additional problem with the BEB method is that an excessive collision error does not indicate that something is wrong with the network. Under the BEB, an excessive collision error is reported whenever a given host experiences 16 collisions in a row. However, the probability of a repeat collision on a retransmission attempt does not decay with the number of retries. Thus, since an excessive collision error is a normal event on a modestly active network, the error is not useful to higher network management functions in the diagnosis of failure conditions.
In view of the foregoing, an object of the present invention is to provide an improved MAC sublayer CSMA/CD protocol which is interoperable with the currently installed Ethernet protocol using the BEB method.
Another object of the present invention is to reduce network delay time and variance while maintaining current throughput capacity.
Yet another object of the present invention is to provide a fairer scheduling discipline to avoid monopolization of the channel by a limited number of hosts while still taking advantage of the capture effect to improve network capacity.
Still another object of the present invention is to decrease the reaction time of a network to a transient overload and to stabilize a network with up to one-thousand and twenty-four hosts.
A further object of the present invention is to make the excessive collision error a useful diagnostic signal.
Additional objects and advantages of the invention will be set forth in the description which follows and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the claims.